package dynamtic;

/**
 * @Author Jun jie Yi
 * 2022/4/6 14:38
 */

public class OneTwoBagProblem {
    public static void main(String[] args) {
        int N = 3, W = 4;
        int[] wt = {2, 1, 3};
        int[] val = {4, 2, 3};
        int knapsack = knapsack(W, N, wt, val);
        System.out.println(knapsack);

    }

    static int knapsack(int W, int N, int[] wt, int[] val) {
        // vector 全填入 0，base case 已初始化
        int[][] dp = new int[N + 1][W + 1];
        for (int i = 1; i <= N; i++) {
            for (int w = 1; w <= W; w++) {
                if (w - wt[i - 1] < 0) {// 当前背包容量装不下，只能选择不装入背包
                    dp[i][w] = dp[i - 1][w];
                } else {// 装入或者不装入背包，择优
                    dp[i][w] = Math.max(dp[i - 1][w - wt[i - 1]] + val[i - 1], dp[i - 1][w]);
                }
            }
        }
        return dp[N][W];
    }
}
